package nodelist

// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnnbp2/
// 合并两个有序链表
// 算法: 直接遍历即可
// 扩展: 如果有多个有序链表怎么办？ -- 用多根堆进行排序
func MergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	if nil == l1 && nil == l2 {
		return nil
	}
	head := new(ListNode)
	currentNode := head
	for nil != l1 || nil != l2 {
		toMoveL1 := true
		if nil != l1 && nil != l2 {
			if l1.Val > l2.Val {
				toMoveL1 = false
			}
		} else if nil != l2 {
			toMoveL1 = false
		}
		currentVal := 0
		if toMoveL1 {
			currentVal = l1.Val
			l1 = l1.Next
		} else {
			currentVal = l2.Val
			l2 = l2.Next
		}
		currentNode.Next = new(ListNode)
		currentNode = currentNode.Next
		currentNode.Val = currentVal
	}
	return head.Next
}
